In multicast and/or broadcast applications, data are transmitted from a server to multiple receivers over wired and/or wireless networks. A multicast system as used herein is a system in which a server transmits the same data to multiple receivers simultaneously, where the receivers form a subset of all the receivers up to and including all of the receivers. A broadcast system is a system in which a server transmits the same data to all of the receivers simultaneously. That is, a multicast system by definition can include a broadcast system.
Data is usually formatted into packets and or frames for transmission. That is, packets and frames are data formatting schemes. As used herein data can be formatted into any convenient format for transmission including packets and/or frames.
Multicast applications such as content distribution, file sharing, data casting, software upgrade, and video multicast are becoming increasingly common. In contrast to unicast, high-throughput reliable multicast in wireless mesh networks (WMNs) has received little attention. Reliable multicast, i.e. the distribution and delivery of data to multiple receivers, in wireless multi-hop networks is very important because it provides many applications to wireless clients (devices, stations, nodes), such as video sharing, content distribution, file download, interactive chat lines, software upgrade, etc. A 100% Packet Delivery Ratio is always in conflict with high throughput in conventional multicast protocols. Multicast data packets are transmitted along different paths with various hops and throughput from the multicast source to different multicast receivers, i.e. the paths from the multicast source to different receivers have various quality characteristics, packet loss rates and throughput. Due to the lossy nature of wireless links, varying channel conditions and interference, reliable multicast is difficult to achieve in multi-hop networks. Another challenge is the “crying babies” problem, which is the notion that a few receivers with particularly bad connections may experience a high packet loss and low throughput. This results in slowing down the whole multicast session in order to ensure that these “crying babies” receive the data transmission. It is thus challenging to achieve reliable and efficient multicast with no loss and high throughput over multi-hop wireless networks because the receivers (“crying babies”) with poor network connectivity and lossy wireless links may greatly degrade the performance of the receivers with good network connectivity.
Traditional reliable multicast techniques are all client and server based. There is no intermediate node interaction. That is, intermediate nodes and/or routers simply forward the data packets. One class of reliable multicast schemes is based on Forward Error Correction (FEC). With FEC, the sender (transmitter, source) transmits (sends, forwards) redundant encoded data packets, and the receivers (sinks, destinations) detect and recover lost data packets in order to reconstruct the original data. No feedback from the receivers and no retransmissions are required. The use of FEC itself cannot guarantee 100% reliability. While the most common form of FEC usually involves Reed-Solomon (RS) codes, at least one FEC scheme for reliable multicast uses a linear code (such as Digital Fountain codes). “In Coding Theory and Communication Theory, fountain codes (also known as rateless erasure codes) are a class of erasure codes with the property that a potentially limitless sequence of encoding symbols can be generated from a given set of source symbols such that the original source symbols can be recovered from any subset of the encoding symbols of size equal to or only slightly larger than the number of source symbols.” (Wikipedia) In such a scheme, the server keeps sending coded data packets for a chunk (unit) of data to multiple receivers and a multicast receiver receives the coded data packets. The receiver leaves (exits) the multicast tree after receiving enough data packets to decode the data (content). The issue is that the server needs to keep transmitting (sending) the data packets for the chunk until the last receiver receives enough data packets to decode the transmission even if only one link is the bottleneck. This is a waste of bandwidth.
Another prior art scheme is based on hybrid ARQ-FEC. A negative acknowledgement (NACK) is often used to reduce the feedback traffic. Receivers send NACKs to the server to request lost or damaged data packets in order to recover the lost or damaged data packets. The term “corrupted data packets” is used herein to include any data packets that have been lost, destroyed or damaged in any way. The server retransmits the FEC coded packets in multicast. Receivers recover their lost data packets using FEC. It is possible that each receiver may have different lost packets that can all be recovered using the same FEC data. However, it may cause a problem known as NACK implosion and delay will be incurred due to the NACK transmissions resulting in delays for the server transmitting and the receivers receiving the FEC data.
It has been shown recently that network coding can increase throughput over a broadcast medium, such as that in wireless networks, by allowing intermediate nodes (routers) to encode data packets instead of simply replicating and forwarding data packets. An intermediate node can mix data packets from different flows into a coded data packet to increase the information content in a transmission and the receivers can decode the original data packets using the coded data packets and the data packets overheard earlier. This is called inter-flow network coding. Inter-flow network coding requires special network topology and flow routes such as “Alice-Bob structure” or X-structure” in order for the receivers to overhear the data packets of different flows and decode the coded data packets. Furthermore, inter-flow network coding requires the transmitter to know what data packets have been overheard or buffered by each of the receivers. These requirements result in certain application limitations of inter-flow network coding and control overhead. More recently, intra-flow network coding based on random linear block codes has attracted some research attention, in which a network router (source and intermediate node) performs random linear coding operations to a block of data packets of a flow, i.e. independently and randomly select linear mappings from inputs onto output over some field, and sends the coded data packets. The primary goal is to bring new information to the receivers in each of the forwarded data packets.
Network coding allows the source and every intermediate node to perform coding operations on data packets it has besides simply replicating and forwarding the data packets. Before the operation, the node usually determines if a received packet is innovative or not before it is added to the linear combination. A packet is said to be innovative if it is linearly independent with respect to other packets by Gaussian elimination. In the other words, the packet brings new information to the node. A receiver can decode the original data as long as it receives or overhears enough innovative data packets from any node (ancestor nodes (parents, grandparents, . . . ) and sibling nodes) along any path (route, link, channel). That is, if the receiver receives as many independent linear combinations as is necessary to reach the full rank of data in the chunk the source has. The full rank equals the number of original packets the source intended to transmit to the receivers. Initial theoretical work in information theory has shown that distributed random linear network coding achieves multicast capacity with probability exponentially approaching 1 with the code length, as well as taking advantage of redundant network capacity for improved success probability and robustness, in general multicast networks. Furthermore, the broadcast medium in wireless networks allows overhearing and opportunistic routing, leading to further performance and protocol design advantages.
Practical design that employs network coding (NC) to ensure reliable multicast in wireless mesh networks is still in the initial stages of research and development. Wireless mesh networks incur lossy and varying channel conditions and interference. That is, some receivers have good wireless connections to the multicast source, but some other receivers have very lossy and low throughput paths to the multicast source. There are many issues surrounding the protocol design with or adaptation to network coding for distributed network resource optimization. In the prior art, a scheme called MORE was the first practical RNC based protocol. MORE uses intra-flow RNC with opportunistic routing. Conventional routing chooses the next-hop before transmitting a data packet but, when link quality is poor, the probability that the chosen next-hop receives the data packet correctly is low. In contrast, opportunistic routing allows any node that overhears the transmission and is closer to the destination to participate in forwarding the data packet to the destination, increasing the throughput. This is called opportunistic routing or opportunistic forwarding or opportunistic delivery. In MORE, any node that overhears the transmission and is closer to the destination can participate in forwarding the data packet to the destination, forming a forwarding belt instead of path. However, multiple nodes may hear a data packet broadcast and unnecessarily forward the same data packet. Belt forwarding can be inefficient, especially for multicast in which multiple overlapped belts are formed. Conventional opportunistic routing protocol, for example, ExOR deals with this issue by imposing a strict media access control (MAC) scheduler on routers' access to the medium, which prevents spatial reuses and makes the protocol less amenable to extensions to alternate traffic types such as multicast although the scheduler delivers opportunistic gains. Instead, to reduce duplicate packets over the air, MORE combines RNC with opportunistic routing with the primary goal of removing the strict MAC scheduling coordination of forwarding routers required in opportunistic routing. MORE randomly mixes packets before forwarding them. This randomness ensures that routers that hear the same transmission do not forward the same data packets. MORE addresses both unicast and multicast routing. However in MORE, multiple intermediate nodes that hear the data packet broadcast forward the coded data packets opportunistically without any coordination. The number of coded data packets sent by an intermediate node may be more than that needed so bandwidth is wasted, or less than that needed so extra delay is introduced for the receiver to receive enough data packets to decode the original data. In addition, MORE lacks source rate limiting which can cause congestion. Furthermore, it suffers from the “crying babies” problem which is unique to multicast.
Pacifier is a state-of-the-art reliable multicast protocol for wireless mesh networks. Pacifer improves upon MORE by using conventional tree-based multicast routing with intra-flow network coding and opportunistic routing (forwarding, delivery). In Pacifier, only the nodes on the multicast tree can perform random linear network coding of incoming data packets and forward the coded data packets along the tree. Pacifer has been proved to be more efficient than MORE. However, similar to MORE, the intermediate nodes do not cooperate with each other and do not send feedback (acknowledgement) of data packet receipt status to their parent nodes. Each node simply estimates the number of coded data packets to transmit to its children (child nodes) per received data packet assuming the expected link loss rate is known. This approach may still result in sending more data packets unnecessarily or less data packets insufficiently. Pacifier also does not consider the impact of physical layer multi-rate to the throughput and link loss rate since Pacifer only deals with the expected data packet loss rate. In Pacifier, a file is divided into batches, e.g. a batch includes 32 data packets. The source iteratively sends the batches in a round-robin manner to deal with the “crying baby” problem. The source switches to the next batch when it receives from one receiver an acknowledgement of completion (complete reception) of the current batch or it transmits the number of coded data packets of this batch more than an estimated limit (counter) value. This approach reduces the “crying baby” problem, but it introduces a set of issues in real situations. Acknowledgements might get lost or delayed due to heavy congestion. The best receiver might not receive the whole batch due to data packet loss when the number of transmitted data packets has reached the limit and the source switches to the next batch. The authors realized this issue, and introduced a tunable knob to set a proper limit (counter) value. However, this tunable knob or the limit (counter) value is hard to estimate, leading to either wasting bandwidth or additional delay. Another issue is that the source switches to the next batch once the source receives an acknowledgement from the best receiver. Other receivers must wait for a whole round before the source transmits data packets from the first batch again. This results in long delays and unfairness for other receivers. If the acknowledgements for the two batches are from two different receivers, the situation becomes even worse and no receiver can quickly obtain the necessary number of data packets to decode all the batches in order and complete the file downloading or content retrieval quickly.
As multicast is becoming increasingly common with content distribution and file sharing applications, new solutions for throughput improvement and better handling of the “crying babies” problem are needed to support these multicast applications in reliable and high-performance ways over multi-hop wireless mesh networks. With dramatic advances in micro-processor and data storage technologies, modern wireless routers are equipped with much more powerful processing capability and data storage capacity at significantly lower prices than even a couple of years ago. Tradeoffs can be made in protocol design for processing power and storage capacity requirements, and bandwidth efficiency performance.